import java.util.*;

public class Solution1104 {

    class Solution {
        private List<List<Integer>> getLevelListTillLabel(int label){
            List<List<Integer>> levelList = new ArrayList<>();
            int mod = 0;
            int rowCount = 1;
            int tmpNum = 1;
            while(tmpNum<=label){
                List<Integer> tmpNums = new LinkedList<>();
                for (int i = tmpNum; i < tmpNum+rowCount; i++) {
                    if(mod%2==0){
                        tmpNums.add(i);
                    }
                    else{
                        tmpNums.add(0,i);
                    }
                }
                levelList.add(tmpNums);
                mod++;
                tmpNum = tmpNum+rowCount;
                rowCount*=2;
            }
            return levelList;
        }

        public List<Integer> pathInZigZagTree(int label) {
            List<List<Integer>> levelList = getLevelListTillLabel(label);
            int level = levelList.size()-1;
            int ind = levelList.get(level).indexOf(label);
            List<Integer> res = new LinkedList<>();
            while(level>=0){
                List<Integer> tmpLevelList = levelList.get(level--);
                res.add(0, tmpLevelList.get(ind));
                ind/=2;
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution1104 s = new Solution1104();
        //s.pathInZigZagTree(14);
    }
}
